package com.zhaopin.theswordreferstooffer;

import java.util.HashSet;
import java.util.Set;

/**
 * @author yin.peide
 * @date 2021-06-18 10:14
 * 面试题28： 字符串的排列   是一个递归问题  TODO 待定，为了不影响进度，最后再看
 */
public class Offer28 {

    public static void main(String[] args) {
        Offer28 offer28 = new Offer28();
        String[] strAttr = offer28.permutation("abc");
        for (String s : strAttr) {
            System.out.println(s);
        }

    }


    /**
     * 架构pdf解法
     * @param s
     * @return
     */
    public String[] permutation(String s) {
        Set<String> res = new HashSet<>();
        backtrack(s.toCharArray(), "", new boolean[s.length()], res);
        return res.toArray(new String[res.size()]);
    }

    /**
     *
     * @param chars 要处理的字符串数组
     * @param temp 选择字符长度的字符串
     * @param visited
     * @param res 最终结果的集合
     */
    private void backtrack(char[] chars, String temp, boolean[] visited, Set<String> res) {
        //边界条件判断，当选择的字符长度等于原字符串长度的时候，说明原字符串的字符都已经
        //选完了
        if (temp.length() == chars.length) {
            res.add(temp);
            return;
        }
        //每一个节点我们都要从头开始选
        for (int i = 0; i < chars.length; i++) {
            //已经选择过的就不能再选了
            if (visited[i]) {
                continue;
            }

            //表示选择当前字符//表示选择当前字符
            visited[i] = true;
            //把当前字符选择后，到树的下一层继续选
            backtrack(chars, temp + chars[i], visited, res);
            //递归往回走的时候要撤销选择
            visited[i] = false;
        }
    }

    //解法2：使用递归替换的方式
    public static void permutation2(){

    }


}
